#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Solution
{
public:
    int findShortestCycle(int n, vector<vector<int>> &edges)
    {
        vector<vector<int>> con(n, vector<int>());
        for (auto e : edges)
        {
            con[e[0]].push_back(e[1]);
            con[e[1]].push_back(e[0]);
        }

        auto minCycle = [n, &con](int start) -> int
        {
            queue<pair<int, int>> q; // index and parent
            vector<int> depth(n, -1);
            q.push({start, -1});
            depth[start] = 0;
            int curDepth = 0;
            int ans = INT_MAX;
            while (!q.empty())
            {
                curDepth++;
                int size = q.size();
                for (int j = 0; j < size; j++)
                {
                    auto [cur, parent] = q.front();
                    q.pop();
                    for (auto next : con[cur])
                    {
                        if (next == parent)
                            continue;
                        if (depth[next] == -1)
                        {
                            depth[next] = curDepth;
                            q.push({next, cur});
                        }
                        else
                        {
                            ans = min(ans, curDepth + depth[next]);
                        }
                    }
                }
            }
            return ans == INT_MAX ? -1 : ans;
        };

        int ans = INT_MAX;
        for (int i = 0; i < n; i++)
        {
            int cur = minCycle(i);
            if (cur != -1)
                ans = min(ans, cur);
        }
        return ans == INT_MAX ? -1 : ans;
    }
};

int main()
{
    cout << "Code2608" << endl;
    Solution s;
    vector<vector<int>> edges = {{0, 1}, {0, 2}, {1, 2}};
    cout << s.findShortestCycle(3, edges) << endl;
    return 0;
}